package com.xiongtian.recursion;

/**
 * @author xiongtian
 * @version 1.0
 * @date 2021/3/25 15:52
 * 八皇后问题
 */
public class Queue8 {

    // 定义一个max表示共有多少个皇后
    int max = 8;
    // 定义数组array，用于保存皇后放置位置的结果，比如：arr[8] = {0,4,7,5,2,6,1,3}
    int[] arr = new int[max];

    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {

        // 测试一把，8皇后是否正确
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法:.", count);
        System.out.println();
        System.out.printf("一共判断冲突的次数：%d.",judgeCount); // 1.5W
    }

    // 编写一个方法，放置第n个皇后
    // 特别注意：每一层check是每一次递归时，进入到check中都有一套for循环，因此会有回溯
    private void check(int n) {
        if (n == max) { // n==8,其实8个皇后已然放好了
            print();
            return;
        }
        // 依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            // 先把当前这个皇后 n ,放到该行的第一列
            arr[n] = i;
            // 判断当放置第n个皇后到i列时是否冲突
            if (judge(n)) { // 不冲突
                // 接着放n+1皇后，开始递归
                check(n + 1);
            }
            // 如果冲突，就继续执行arr[n] = i;即将第n个皇后，放置在本行的后一个位置
        }
    }

    //查看我们放置第n个皇后时就去检测该皇后是否和前面已经摆放的皇后冲突

    /**
     * @param n 表示放第n个皇后
     * @return
     */
    private boolean judge(int n) {
        judgeCount++;
        // TODO :注意是n不是8，只需要检测到第n个即可
        for (int i = 0; i < n; i++) {
            // 说明
            // 1. arr[i] ==arr[n] 表示判断 第n个皇后是否和前面n-1个皇后在同一列
            // 2. Math.abs(n-i)==Math.abs(arr[n]-arr[i]) 表示判断第n个皇后和第i个皇后是否在同一斜线
            // 3. 判断是否在同一行，没有必要判断，n每次都在递增
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    // 写一个方法,可以将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
}
